import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {
    static class DLinkNode {
        public int key;
        public int val;
        public DLinkNode prev;
        public DLinkNode next;

        public DLinkNode(){}

        public DLinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public DLinkNode head, tail;
    public int usedSize;
    public Map<Integer,DLinkNode> cache;
    public int capacity;


    public LRUCache(int capacity) {
        this.head = new DLinkNode();
        this.tail = new DLinkNode();
        this.cache = new HashMap<>();
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    private void moveToHead(DLinkNode node) {
        //先将该节点从原来的位置删除掉
        removeNode(node);
        //然后将该节点添加到head
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void removeNode(DLinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void put(int key, int value) {
        DLinkNode node = cache.get(key);
        if (node == null) {
            DLinkNode newNode = new DLinkNode(key,value);
            cache.put(key,newNode);
            newNode.next = head.next;
            head.next.prev = newNode;
            head.next = newNode;
            newNode.prev = head;
            usedSize++;
            //如果当前节点的元素个数大于capacity，那么删除tail节点
            if (usedSize > capacity) {
                cache.remove(tail.prev.key);
                tail.prev.prev.next = tail;
                tail.prev = tail.prev.prev;
                usedSize--;
            }
        }else {
            node.val = value;
            moveToHead(node);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
